package com.chenjun.year2018.january.day13;

public class LSC {
    public static void main(String[] args) {
        String s1 = "ABCBDAB", s2 = "BDCABA";
        int[][] c = lengthLCS(s1, s2);
        printLSC(c, s1, s1.length(), s2.length());
    }

    //求LCS的长度
    private static int[][] lengthLCS(final String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] c = new int[m + 1][n + 1];

        /*处理特殊的0行和0列*/
        for (int i = 0; i <= m; i++)
            c[i][0] = 0;
        for (int j = 0; j <= n; j++)
            c[0][j] = 0;

        /*处理其他行和列*/
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    c[i][j] = c[i - 1][j - 1] + 1;
                } else {
                    if (c[i - 1][j] >= c[i][j - 1])
                        c[i][j] = c[i - 1][j];
                    else
                        c[i][j] = c[i][j - 1];
                }
            }
        }
        System.out.println(c[m][n]);
        return c;
    }

    private static void printLSC(int[][] c, String s1, int i, int j) {
        if (i == 0 || j == 0) return;
        int max = c[i][j];//最大值
        if (c[i - 1][j] == max) {
            //如果上方的数相等，向上移动
            printLSC(c, s1, i - 1, j);
        } else if (c[i][j - 1] == max) {
            //如果左方的数相等，向左移动
            printLSC(c, s1, i, j - 1);
        } else if (c[i - 1][j - 1] == max) {
            //如果左上方的数相等，向左上移动
            printLSC(c, s1, i - 1, j - 1);
        } else {
            //向左上移动
            printLSC(c, s1, i - 1, j - 1);
            System.out.print(s1.charAt(i - 1));
        }
    }
}
